package org.regotto.basics.dataStruct;

/**
 * trie 树, son 数组二维大小由树的分叉决定
 */
public class Trie {

    // 此处应对 26 个英文字母, 存在 26 个分叉
    static int[][] son = new int[1000][26];
    static int[] cnt = new int[1000];
    static int idx;

    public static void I(char[] s) {
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int u = s[i] - 'a';
            if (son[p][u] == 0) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }

    public static int Q(char[] s) {
        int p = 0;
        for (int i = 0; i < s.length; i++) {
            int u = s[i] - 'a';
            if (son[p][u] == 0) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }

    // 向集合中插入x, 求x出现次数
    public static void main(String[] args) {
        I("abc".toCharArray());
        I("abc".toCharArray());
        I("def".toCharArray());
        System.out.println(Q("abc".toCharArray()) + " " + Q("def".toCharArray()) + " " + Q("a".toCharArray()));
    }

}
